'''
使用层级遍历法，查找树的最宽层是多少个节点

'''

from collections import deque


class Node :
    def __init__(self, data: int): 
        self.value = data
        self.left = None
        self.right = None
def maxwidth_usemap(head: Node) -> int:
    if not head: return 0
    queue = deque()
    queue.append(head)
    level_map = {head: 1}  #记录节点的层级
    cur_level = 1 #当前正在统计哪一层
    cur_level_nodes = 0 # 当节点出队时开始统计节点个数
    max_nodes = 0
    while len(queue) > 0:
        cur = queue.popleft()
        cur_node_level = level_map[cur] #当前节点的层
        if cur.left:
            level_map[cur.left] = cur_node_level + 1
            queue.append(cur.left)
        if cur.right:
            level_map[cur.right] = cur_node_level + 1
            queue.append(cur.right)        
        if cur_node_level == cur_level: #如果 当前节点所在层==当前统计层
            cur_level_nodes += 1
        else:  #通过设置flag方式来发现某一层结束
            max_nodes = max(max_nodes, cur_level_nodes) #上一层的最大个数
            cur_level += 1
            cur_level_nodes = 1  #当前层的节点个数
    max_nodes = max(max_nodes, cur_level_nodes)
    return max_nodes
def maxwidth_nomap(head: Node) -> int:
    if not head: return 0
    queue = deque()
    queue.append(head)
    cur_end = head # 当前层的最右节点
    next_end = None # 下一层的最后节点
    max_nodes = 0
    cur_level_nodes = 0
    while len(queue) > 0:
        cur = queue.popleft()
        if cur.left:
            next_end = cur.left
            queue.append(cur.left)
        if cur.right:
            next_end = cur.right
            queue.append(cur.right)  
        cur_level_nodes += 1  # 统计cur , 弹出时统计
        if cur == cur_end: #通过设置flag方式来发现某一层结束
            max_nodes = max(max_nodes, cur_level_nodes)      
            cur_level_nodes = 0  #下一层还没有开始统计
            cur_end = next_end   #下一层的最右变成当前层的最右
    return max_nodes

#打印二叉树 
def getSpace(num: int) -> str:
    # return f'|{" "*num}|'
    return f'|{" "*num}|'
def printInOrder(head: Node, height: int, to: int, length: int):
    if not head :  return
    printInOrder(head.right, height + 1, "v", length)
    val = to + str(head.value) + to
    lenM = len(val)
    lenL = (length-lenM) >> 1
    lenR = length - lenM - lenL
    val = getSpace(lenL) + val + getSpace(lenR)
    print(getSpace(height * length) + val)
    printInOrder(head.left, height + 1, "^", length)
def printTree(head: Node) :
    print("Binary Tree:")
    printInOrder(head, 0, "H", length=17)

def main():
    head =  Node(4)
    head.left =  Node(2)
    head.right =  Node(6)
    head.left.left =  Node(1)
    head.left.right =  Node(3)
    head.right.left =  Node(5)
    head.right.right =  Node(7)
    printTree(head)
    print(maxwidth_usemap(head))
    print(maxwidth_nomap(head))
main()

'''
已知一棵完全二叉树，求其节点的个数 要求：时间复杂度低于O(N)，N为这棵树的节点个数
'''
class Node :
    def __init__(self, data: int): 
        self.value = data
        self.left = None
        self.right = None
# head 节点是第一层
def mostLeftLevel(node: Node, level: int) -> int:
    while node:
        level += 1
        node = node.left
    return level - 1

# h总的层数
def bs(node: Node, l: int, h: int)-> int:
    if l == h: return 1
    if (mostLeftLevel(node.right, l + 1) == h) :  # 如果右节点的做子树的的高度== 本树的高度-1
        return (1 << (h - l)) + bs(node.right, l + 1, h) # 1 << (h - l)) 左子树的节点个数
    else :
    	return (1 << (h - l - 1)) + bs(node.left, l + 1, h)  # 如果右节点的做子树的的高度不等于本树的高度-1
        #1 << (h - l - 1)) 右子树的节点个数

def nodeNum(head: Node) -> int:
    if not head : return 0
    return bs(head, 1, mostLeftLevel(head, 1))

def main():
    head =  Node(1)
    head.left =  Node(2)
    head.right =  Node(3)
    head.left.left =  Node(4)
    head.left.right =  Node(5)
    head.right.left =  Node(6)
    print(nodeNum(head))
main()


'''
设计RandomPool结构 【题目】 设计一种结构，在该结构中有如下三个功能： insert(key)：将某个key加入到该结构，做到不重复加入。
 delete(key)：将原本在结构中的某个key移除。
 getRandom()： 等概率随机返回结构中的任何一个key。 
【要求】 Insert、delete和getRandom方法的时间复杂度都是 O(1)
'''
import random
class Pool:
    def __init__(self):
        self.keyIndexMap = {}
        self.indexKeyMap = {}
        self.size = 0
    def insert(self, key: str) :
        if key not in self.keyIndexMap:
            self.keyIndexMap[key] = self.size
            self.indexKeyMap[self.size] = key
            self.size += 1
        
    def delete(self, key: str) :
        if key in self.keyIndexMap :
            deleteIndex = self.keyIndexMap.get(key)
            lastIndex = self.size - 1
            lastKey = self.indexKeyMap.get(lastIndex) #最后一个元素的内容
            self.keyIndexMap[lastKey] = deleteIndex
            self.indexKeyMap[deleteIndex] = lastKey
            self.keyIndexMap.pop(key)
            self.indexKeyMap.pop(lastIndex)
            self.size = lastIndex
    def getRandom(self) :
        if not self.size :return None
        randomIndex = (int) (random.random() * self.size)   # 0 ~ size -1
        print(randomIndex)
        return self.indexKeyMap.get(randomIndex)
def main():
    pool = Pool()
    pool.insert("zuo")
    pool.insert("cheng")
    pool.insert("yun")
    # print(pool.getRandom())
    # print(pool.getRandom())
    # print(pool.getRandom())
    # print(pool.getRandom())
    # print(pool.getRandom())
    # print(pool.getRandom())
    pool.delete('zuo')
    print('=================')
    print(pool.getRandom())
    print(pool.getRandom())
    print(pool.getRandom())
    print(pool.getRandom())
    print(pool.getRandom())
    print(pool.getRandom())   
main()

'''
岛问题 一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右 四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，
求一个 矩阵中有多少个岛？
'''
##暴力解法
# def countIslands(m: list[list]) -> int: 
#     if not m or not m[0] : 	return 0
#     N = len(m) #行
#     M = len(m[0]) #列
#     res = 0
#     for i in range(N) :
#         for j in range(M):
#             if m[i][j] == 1:
#                 res += 1
#                 infect(m, i, j, N, M)
#     return res

# def infect(m: list[list], i: int, j: int, N: int, M: int) :
#     if i < 0 or i >= N or j < 0 or j >= M or m[i][j] != 1: return
#     m[i][j] = 2
#     infect(m, i + 1, j, N, M)
#     infect(m, i - 1, j, N, M)
#     infect(m, i, j + 1, N, M)
#     infect(m, i, j - 1, N, M)
# def main():
#     m1 = [  [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
#             [ 0, 1, 1, 1, 0, 1, 1, 1, 0 ], 
#             [ 0, 1, 1, 1, 0, 0, 0, 1, 0 ],
#             [ 0, 1, 1, 0, 0, 0, 0, 0, 0 ], 
#             [ 0, 0, 0, 0, 0, 1, 1, 0, 0 ], 
#             [ 0, 0, 0, 0, 1, 1, 1, 0, 0 ],
#             [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ], ]
#     print(countIslands(m1))
#     m2 = [  [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ], 
#             [ 0, 1, 1, 1, 1, 1, 1, 1, 0 ], 
#             [ 0, 1, 1, 1, 0, 0, 0, 1, 0 ],
#             [ 0, 1, 1, 0, 0, 0, 1, 1, 0 ], 
#             [ 0, 0, 0, 0, 0, 1, 1, 0, 0 ], 
#             [ 0, 0, 0, 0, 1, 1, 1, 0, 0 ],
#             [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ], ]
#     print(countIslands(m2))
# main()

'''
并查集，使用并查集解决岛问题
'''
from types import NoneType


class Node:
    def __init__(self) -> None:
        pass
class UnionFindSet :
    def __init__(self, nodes: list):
        # self.__fatherMap = {}
        # self.__sizeMap = {} # 只有顶点元素需要记录size
        self.__makeSets(nodes)
    def __makeSets(self, nodes: list) :
        self.__fatherMap.clear()
        self.__sizeMap.clear()
        for node in nodes:
            self.__fatherMap[node] = node
            self.__sizeMap[node] =1

def __findHead(self, node: NoneType) -> NoneType:
    father = self.__fatherMap.get(node)
    if father != node:
        father = self.__findHead(father)
    self.__fatherMap[node] = father
    return father
#可以使用非递归实现__findHead
# def  __findHead(self, node: NoneType) -> NoneType:
#     path = []
#     while self.__fatherMap.get(node) != node:
#         path.append(node)
#         node = self.__findHead(node)
#     while len(path) > 0:
#         self.__fatherMap[path.pop()] = node
#     return node
	
def isSameSet(self,a: NoneType, b: NoneType) -> bool:
    return self.__findHead(a) == self.__findHead(b)
def union(self,a: NoneType, b: NoneType):
    if not a or not b : return	
    aHead = self.__findHead(a)
    bHead = self.__findHead(b)
    if aHead != bHead:
        aSetSize = self.__sizeMap.get(aHead)
        bSetSize = self.__sizeMap.get(bHead)
        if (aSetSize <= bSetSize) :
            self.__fatherMap[aHead] = bHead
            self.__sizeMap[bHead] = aSetSize + bSetSize
            self.__sizeMap.pop(aHead)
        else :
            self.__fatherMap[bHead] = aHead
            self.__sizeMap[aHead] = aSetSize + bSetSize
            self.__sizeMap.pop(bHead)